Liste Simplement Chainée¶

Principe¶

Les listes chainées se libèrent de la contrainte de stocker les éléments dans des emplacements contigus en mémoire.

Bénéfice: Aucun déplacement nécessaire pour insérer ou supprimer

Coûts:

stocker explicitement l'emplacement de l'élément suivant
avancer de $k$ positions = passer $k$ fois à l'élément suivant
utilisation moins efficace de la mémoire cache

Les éléments de la liste sont stockés indivuellement dans les maillons de la chaine. Chaque maillon stocke

l'élément
un pointeur vers le maillon suivant

In [1]:

class Maillon:
    def __init__(self,valeur):
        
        self.donnee = valeur       
        
        self.suivant = None

Cette structure suffit à constuire une liste manuellement. Construisons

In [3]:

tete = Maillon(12) 
tete.suivant = Maillon(99) 
tete.suivant.suivant = Maillon(37)

Parcours¶

Pour traverser tous les éléments d'une liste, il faut

traiter le maillon courant
passer au maillon suivant
jusqu'à ce que l'on atteigne un maillon nul

On peut l'écrire récursivement

In [4]:

def afficher(M):
    if M != None:
        print(M, end = " → ")
        afficher(M.suivant)
    else:
        print("⌀")

In [5]:

afficher(tete)

12 → 99 → 37 → ⌀

Mieux, on peut l'écrire itérativement

In [6]:

def afficher(M):
    while M != None:
        print(M, end = " → ")
        M = M.suivant
    print("⌀")

In [7]:

afficher(tete)

12 → 99 → 37 → ⌀

Opérations en tête¶

Insérer et supprimer en tête sont des opérations simples.

Pour insérer, on doit

créer un nouveau maillon qui deviendra la tête
faire de l'ancienne tête le maillon suivant la nouvelle tête

In [8]:

def inserer_en_tete(ancienne_tete, valeur):
    
    nouvelle_tete = Maillon(valeur)
    
    nouvelle_tete.suivant = ancienne_tete
    
    return nouvelle_tete

In [9]:

afficher(tete)

12 → 99 → 37 → ⌀

In [10]:

tete = inserer_en_tete(tete,25)
afficher(tete)

25 → 12 → 99 → 37 → ⌀

Pour supprimer en tête il suffit de remplacer la tête par l'élément suivant

In [11]:

def supprimer_en_tete(ancienne_tete):
    assert(ancienne_tete)
    
    nouvelle_tete = ancienne_tete.suivant
    
    return nouvelle_tete

In [12]:

afficher(tete)

25 → 12 → 99 → 37 → ⌀

In [13]:

tete = supprimer_en_tete(tete)
afficher(tete)

12 → 99 → 37 → ⌀

Opérations en position quelconque¶

Insérer ou supprimer après un maillon connu est également efficace.

Pour insérer un élément derrière le maillon M, il faut

créer un nouveau maillon
insérer ce maillon entre M et M.suivant

In [14]:

def inserer_apres(M, valeur):
    assert(M)
    
    nouveau = Maillon(valeur)
    
    nouveau.suivant = M.suivant
    
    M.suivant = nouveau

In [15]:

afficher(tete)

12 → 99 → 37 → ⌀

In [16]:

inserer_apres(tete.suivant,42)
afficher(tete)

12 → 99 → 42 → 37 → ⌀

Pour supprimer l'élément suivant le maillon M, il suivit de faire pointer M.suivant vers l'élément suivant celui à supprimer

In [17]:

def supprimer_apres(M):
    
    assert(M != None and M.suivant != None)
    
    M.suivant = M.suivant.suivant

In [18]:

afficher(tete)

12 → 99 → 42 → 37 → ⌀

In [19]:

supprimer_apres(tete)
afficher(tete)

12 → 42 → 37 → ⌀

Cette opération nous permet de faire des traitement complexes comme ôter les éléments se répétant en positions successives (comme std::unique en C++)

In [20]:

def oter_repetitions(M):
    while M != None and M.suivant != None:
        if M.donnee == M.suivant.donnee:
            supprimer_apres(M)
        else:
            M = M.suivant

In [22]:

afficher(zeros_un_deux)

1 → 1 → 1 → 0 → 0 → 0 → 2 → 2 → 1 → 1 → 0 → ⌀

In [23]:

oter_repetitions(zeros_un_deux)
afficher(zeros_un_deux)

1 → 0 → 2 → 1 → 0 → ⌀

Classe `forward_list`¶

In [24]:

tete = inserer_en_tete(tete,25)

pour l'insertion est source d'erreur. Il est trop facile d'oublier tete =

La classe forward_list stocke et gère le maillon de tête, plus éventuellement d'autre information comme le nombre d'éléments.

In [25]:

class forward_list:
    def __init__(self):
        self.t = None 
        
    def push_front(self,val):
        self.t = inserer_en_tete(self.t,val); 

    def pop_front(self):
        self.t = supprimer_en_tete(self.t); 
        
    def insert_after(self,m,val):
        inserer_apres(m,val); 

    def erase_after(self,m):
        supprimer_apres(m); 
        
    def empty(self): return self.t == None

In [27]:

L = forward_list()
for i in range(6):
    L.push_front(i%3)
print(L)

2 → 1 → 0 → 2 → 1 → 0 → ⌀

In [28]:

L.pop_front()
print(L)

1 → 0 → 2 → 1 → 0 → ⌀

Itérer sur une liste¶

Pour rendre cette classe réellement utile, il faut pouvoir boucler sur ses éléments indépendamment de sa structure interne.

Pour cela, nous introduisons les fonctions suivantes qui cachent les notions de maillon, de tête de chaine, ...

In [29]:

def debut(L):   return L.t

def fin(L):     return None

def suivant(m): return m.suivant

def getv(m):    return m.donnee

def setv(m,v):  m.donnee = v

On peut ré-écrire la fonction d'affichage

In [30]:

def afficher(L):
    m = debut(L)
    while m != fin(L):
        print(getv(m), end=" → ")
        m = suivant(m)
    print("⌀")
    
afficher(L)

1 → 0 → 2 → 1 → 0 → ⌀

Une fonction qui incrémente tous les éléments

In [31]:

def incrementer_tout(L):
    m = debut(L)
    while m != fin(L):
        setv(m, getv(m)+1)
        m = suivant(m)

print(L); incrementer_tout(L); print(L)

1 → 0 → 2 → 1 → 0 → ⌀
2 → 1 → 3 → 2 → 1 → ⌀

Une fonction qui insère un zèro après chaque un.

In [32]:

def inserer_zero_apres_un(L):
    m = debut(L)
    while m != fin(L):
        if getv(m) == 1:
            L.insert_after(m,0)
        m = suivant(m)

print(L); inserer_zero_apres_un(L); print(L)

2 → 1 → 3 → 2 → 1 → ⌀
2 → 1 → 0 → 3 → 2 → 1 → 0 → ⌀

Une fonction qui supprime tous les éléments de valeur 'val'

In [33]:

def supprimer_valeurs(L,val):
    m = debut(L)
    while m != fin(L):
        if suivant(m) and getv(suivant(m)) == val:
            L.erase_after(m)
        else: m = suivant(m)
            
print(L); supprimer_valeurs(L,0); print(L)

2 → 1 → 0 → 3 → 2 → 1 → 0 → ⌀
2 → 1 → 3 → 2 → 1 → ⌀

Mais attention, cette fonction n'est pas correctement écrite. Essayons de supprimer la valeur 2

In [34]:

print(L); supprimer_valeurs(L,2); print(L)

2 → 1 → 3 → 2 → 1 → ⌀
2 → 1 → 3 → 1 → ⌀

La valeur en tête n'est pas supprimée.

Il est impossible avec le faire avec erase_after, puisqu'elle est en tête et pas après un autre maillon.

Comment faire?

ré-écrire supprimer_valeurs ?

ré-écrire la classe forward_list !

`forward_list` améliorée¶

Le problème étant que l'on avait pas de maillon avant la tête, la solution est simple: placer un maillon avant la tête qui

ne stocke pas d'élément
stocke un lien vers le maillon de tête dans son attribut suivant.

Le plus proprement possible, il a son propre type

In [35]:

class MaillonVide:
    def __init__(self):
        
        self.suivant = None

In [36]:

class forward_list:
    def __init__(self):
        self.av = MaillonVide() # avant tête
                
    def insert_after(self,m,val):
        inserer_apres(m,val); 
                
    def erase_after(self,m):
        supprimer_apres(m); 
     
    def push_front(self,val):
        self.insert_after(self.av,val)

    def pop_front(self):
        self.erase_after(self.av)
        
    def empty(self): 
        return self.av.suivant == None

Pour itérer, on introduit une nouvelle fonction avant_debut et on redéfinit debut. Les autres sont inchangées

In [38]:

def avant_debut(L): return L.av

def debut(L):   return suivant(avant_debut(L))

def fin(L):     return None

def suivant(m): return m.suivant

def getv(m):    return m.donnee

def setv(m,v):  m.donnee = v

La fonction supprimer_valeur se réécrit en itérant depuis avant_debut(L)

In [39]:

def supprimer_valeurs(L,val):
    courant = avant_debut(L)
    precedent = courant
    while courant != fin(L):
        courant = suivant(courant)
        if courant and getv(courant) == val:
            L.erase_after(precedent)
        else:
            precedent = courant

In [41]:

L = forward_list()
for i in range(8): 
    L.push_front(i%3)
print(L)

1 → 0 → 2 → 1 → 0 → 2 → 1 → 0 → ⌀

In [42]:

supprimer_valeurs(L,1)
print(L)

0 → 2 → 0 → 2 → 0 → ⌀

Classe `fl_iterator`¶

Il est plus pratique d'utiliser des objets que des fonctions pour itérer. La classe fl_iterator

gère un pointeur vers un des maillons
met en oeuvre getv et setv
sépare la fonction suivant en incr, copie et suivant
met en oeuvre l'opérateur d'égalité pour pouvoir arrêter nos boucles.

In [43]:

class fl_iterator:
    def __init__(self,maillon):
        self.M = maillon
    def getv(self): 
        return self.M.donnee
    def setv(self,val):
        self.M.donnee = val   
    def incr(self): 
        self.M = self.M.suivant
    def copie(self): 
        return fl_iterator(self.M)  
    def suivant(self, N = 1):
        s = self.copie(); 
        for i in range(N): s.incr()
        return s;  
    def __eq__(self,other):
        return isinstance(other,fl_iterator) \
               and self.M == other.M

In [56]:

class forward_list:
    def __init__(self):
        self.av = MaillonVide() 
    def before_begin(self):
        return fl_iterator(self.av)
    def begin(self):
        return fl_iterator(self.av.suivant)
    def end(self):
        return fl_iterator(None)
    def insert_after(self,it,v):
        inserer_apres(it.M,v);         
    def erase_after(self,it):
        supprimer_apres(it.M); 
    def push_front(self,v):
        self.insert_after(self.before_begin(),v)
    def pop_front(self):
        self.erase_after(self.before_begin())

La fonction supprimer_valeur précédente se réécrit alors

In [58]:

def supprimer_valeurs(L,val):
    prec = L.before_begin()
    it = prec.suivant()
    while it != L.end():
        if it.getv() == val: 
            L.erase_after(prec)
        else: 
            prec = it
        it = prec.suivant()

In [59]:

L = forward_list()
for i in range(8):
    L.push_front(i%3)
print(L);

1 → 0 → 2 → 1 → 0 → 2 → 1 → 0 → ⌀

In [60]:

supprimer_valeurs(L,1); 
print(L)

0 → 2 → 0 → 2 → 0 → ⌀

Copie de liste¶

La copie complète d'un liste peut paraitre simple, mais une approche naive ne fonctionne pas

In [61]:

def copie_liste_naive(L):
    C = forward_list()
    it = L.begin();
    while it != L.end():
        C.push_front(it.getv())
        it.incr()
    return C

In [63]:

L1 = forward_list()
for i in range(8): 
    L1.push_front(i%3)
print(L1);

1 → 0 → 2 → 1 → 0 → 2 → 1 → 0 → ⌀

In [64]:

L2 = copie_liste_naive(L1); 
print(L2)

0 → 1 → 2 → 0 → 1 → 2 → 0 → 1 → ⌀

Pour ne pas inverser, il faut insérer en queue - pas en tête - donc se souvenir du dernier élément de la liste en construction.

In [65]:

def copie_liste(L):
    C = forward_list()
    it = L.begin();
    last_of_C = C.before_begin()
    while it != L.end():
        C.insert_after(last_of_C,it.getv())
        last_of_C.incr()
        it.incr()
    return C

In [67]:

print(L1);

1 → 0 → 2 → 1 → 0 → 2 → 1 → 0 → ⌀

In [68]:

L2 = copie_liste(L1); 
print(L2)

1 → 0 → 2 → 1 → 0 → 2 → 1 → 0 → ⌀

Conclusions¶

Une liste simplement chainée utilise comme maillons des structures stockant individuellement

un élément
un lien vers l'élément suivant

Les opérations efficaces en $\Theta(1)$ sont

insertion et suppression en tête
insertion et suppression après une position connue

Il n'y a ni pas d'accès indexé ou d'opération en queue.

La mise en oeuvre de l'itération et l'utilisation d'un noeud vide en tête simplifient l'utilisation de la structure.

ASD1 Notebooks on GitHub.io